# Метод Ньютона

Метод Ньютона — это итерационный численный метод нахождения корня (нуля) заданной функции. 
Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. 
Также метод Ньютона может быть использован для решения задач оптимизации, в которых требуется определить ноль первой производной либо градиента в случае многомерного пространства.

Алгоритм нахождения численного решения уравнения `f(x)=0` сводится к итерационной процедуре вычисления:

\\(x\_{n+1} = x\_{n} - \frac{f(x\_{n})}{f'(x\_{n})}\\)

**Алгоритм:**

- Задается начальное приближение \\(x\_{0}\\).
- Пока не выполнено условие остановки (например, погрешность в нужных пределах), вычисляется новое приближение по формуле выше.

Чтобы реализовать метод Ньютона в виде процедуры, сначала нужно выразить понятие производной. 
В общем случае, если `g` есть функция, а `dx` — маленькое число, то
производная `Dg` функции `g` есть функция, 
значение которой в каждой точке `x` описывается формулой (при `dx`, стремящемся к нулю):
\\(\frac{g(x + \partial x) - g(x)}{\partial x} \\)

**Код:**

```dotty
object NewtonsMethod:
  private val dx = 1e-6

  def derivative(x: Double, g: Double => Double): Double =
    (g(x + dx) - g(x)) / dx
```

С помощью `derivative` можно выразить метод Ньютона как процесс поиска неподвижной точки:

```dotty
object NewtonsMethod:
  private val accuracy = 1e-6

  @scala.annotation.tailrec
  def newtonsMethod(g: Double => Double, guess: Double): Double =
    val next = transform(g)(guess)
    if math.abs(next - guess) < accuracy then next
    else newtonsMethod(g, next)

  private def transform(g: Double => Double): Double => Double =
    x => x - g(x) / derivative(x, g)
```

**Оценка:**

- **Время** - ???
- **Память** - ???

**Пояснение:**

Рассмотрим задачу о нахождении положительных x, для которых \\(cos x=x^{3}\\). 
Эта задача может быть представлена как задача нахождения нуля функции \\(f(x)=cos x - x^{3}\\). 
Так как \\(cos x \leqslant 1\\) для всех x и \\(x^{3} > 1\\) для x > 1, 
очевидно, что решение лежит между 0 и 1. 
Возьмём в качестве начального приближения значение \\(x\_{0}=0,5\\), тогда:

```dotty
val g: Double => Double = x => math.cos(x) - x * x * x

newtonsMethod(g, 0.5) // 0.865474033101...
```

**Метрики:**

Поиск решения вышеописанной задачи выполняется за 0,2 секунды.

```dotty
private val g: Double => Double = x => math.cos(x) - x * x * x

@main def newtonsMethodBench(): Unit =
  println(newtonsMethod(g, 0.5))

// CPU Time: 216 ms
// Allocation memory size: 9,11 MB      
```

---

**Ссылки:**

- [Метод Ньютона - wiki](https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%9D%D1%8C%D1%8E%D1%82%D0%BE%D0%BD%D0%B0)
- [SICP: Абельсон Х., Сассман Д. - Структура и интерпретация компьютерных программ][sicp]

[sicp]: https://web.mit.edu/6.001/6.037/sicp.pdf